namespace MLRB {
	int Pow(int x,int t, int P){int r=1;for(;t;t>>=1,x=1ll*x*x%P)if(t&1)r=1ll*r*x%P;return r;}
	int Mul(int x, int t, int P) {int r=1; for(;t;t>>1,x=x*2%P)if(t&1)r=(r+x)%P;return r;}

	bool mlrb (int n) {  
		if (n < 2) return false;  
		if (n == 2) return true;  
		if (n % 2 == 0) return false;  
		for (int i = 0; i < 20; i++) {  
			int a = rand() % (n - 1) + 1;  
			if (Pow(a, n - 1, n) != 1)  
				return false;  
		}  
		return true;  
	}  
}
